package offer;

@FunctionalInterface
public interface Partition {
    /**
     *
     * @param head 不带头节点的链表
     * @param x 枢轴元素
     * @return 划分后的链表
     */
    ListNode partition(ListNode head, int x);
}
class PartitionImpl1 implements Partition{

    /**
     * 利用两个虚头节点，小于x的挂到一侧，大于等于x挂到另一侧，由于题目要求保持元素相对顺序，因此使用尾插法
     * @param head 不带头节点的链表
     * @param x 枢轴元素
     * @return 划分后的链表
     */
    @Override
    public ListNode partition(ListNode head, int x) {

        ListNode left = new ListNode(0);
        ListNode leftTail = left;
        ListNode right = new ListNode(0);
        ListNode rightTail = right;
        ListNode cur;
        while(head != null){
            cur = head;
            head = head.next;
            if(cur.val < x){
                leftTail.next = cur;
                leftTail = cur;
            }else{
                rightTail.next = cur;
                rightTail = cur;
            }
        }
        // 枢轴右侧链表尾部置空，否则可能会出现环
        rightTail.next = null;
        // 枢轴左侧链表尾部链接数轴右侧的链表头
        leftTail.next = right.next;
        return left.next;

    }
}
